/*
    Geocache: some utilities for managing and visualizing geocache information
    Copyright (C) 2008  Gary Jackson

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
/*
 * Polygon.java
 */

package com.thegbomb.sphere;

import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Represents a polygon on the surface of a sphere
 * @author Gary Jackson
 */
public class Polygon {
    private Point[] vertices;
    private Orthodrome[] edges;
    private Double area = null;
    private Boolean selfIntersects = null;
    private double perimiter = 0.0d;
    
    /**
     * Creates a new instance of Polygon
     */
    public Polygon(List<Point> pointList) {
        if (pointList.size() < 3)
            throw new SphereException("polygons with fewer than three vertices are not allowed");
        
        vertices = new Point[pointList.size()];
        edges = new Orthodrome[pointList.size()];
        
        Point p = pointList.get(pointList.size() - 1);
        int index = 0;
        for (Point q: pointList) {
            vertices[index] = q;
            edges[index] = new Orthodrome(p, q);
            perimiter += edges[index].length();
            p = q;
            index++;
        }
    }
    
    public List<Point> getPoints() {
        List<Point> pointList = Arrays.asList(this.vertices);
        return Collections.unmodifiableList(pointList);
    }
    
    /**
     * This returns the area of the polygon.  The return value of this function is only meaningful if isSelfIntersecting() is false.  Otherwise, the output is undefined but the function will terminate without error.
     * @return The area of the polygon
     */
    public double getArea() {
        if (area == null)
            area = computeArea();
        return area;
    }
    
    /**
     * This returns the perimiter of the polygon.  The return value is the sum of the length of the orthodromes that comprise the polygon, and is always meaningful.
     * @return the perimiter of the polygon
     */
    public double getPerimiter() { 
        return perimiter;
    }
    
    /**
     * Returns true if the polygon self-intersects.  This uses an O(n ** 2) algorithm, since we do no indexing.
     */
    public boolean isSelfIntersecting() {
        if (selfIntersects == null)
            selfIntersects = computeSelfIntersects();
        return selfIntersects;
    }
    
    private double angle(Orthodrome AB, Orthodrome BC) {
        assert AB.getB() == BC.getA();
        Point B = AB.getB();
        Point D = AB.axis().normal(BC.axis());
        double delta = Math.PI - AB.axis().distance(BC.axis());
        if (AB.axis().equals(BC.axis())) {
            return Math.PI;
        } else if (B.equals(D, 1E-1)) {
            return delta;
        } else {
            return 2 * Math.PI - delta;
        }
    }

    private double computeArea() {
        double sum = angle(edges[edges.length - 1], edges[0]);
        for (int i = 0; i < edges.length - 1; i++) {
            double tmp = angle(edges[i], edges[i+1]);
            sum += tmp;
        }
        return sum - (vertices.length - 2) * Math.PI;
    }

    private Boolean computeSelfIntersects() {
        for (int i = 0; i < edges.length; i++) {
            for (int j = 0; j < i; j++) {
                if (edges[i].intersects(edges[j], Util.TOLERANCE, false))
                    return true;
            }
        }
        return false;
    }
}
